package club.vann.nowcoder;

import club.vann.nowcoder.common.TreeNode;

/**
 * <p>难度：Medium</p>
 * <p>题目：在二叉树中找到两个节点的最近公共祖先</p>
 * <p>描述：给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
 * 注：本题保证二叉树中每个节点的val值均不相同。
 * 示例1
 * 输入：
 * [3,5,1,6,2,0,8,#,#,7,4],5,1
 * 复制
 * 返回值：
 * 3</p>
 * @author vann
 * @Title:
 * @Description:
 * @date 2021/6/16 09:48
 */
public class NC102 {
    public static void main(String[] args) {
        NC102 nc = new NC102();

        System.out.println("Result["+TestCase.ANS+"] : " + nc.lowestCommonAncestor(TestCase.NODE, TestCase.O1, TestCase.O2));
    }

    /**
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null) {
            return Integer.MIN_VALUE;
        }

        if(root.val == o1 || root.val == o2) {
            return root.val;
        }

        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);

        if(left == Integer.MIN_VALUE) {
            return right;
        }

        if(right == Integer.MIN_VALUE) {
            return left;
        }
        return root.val;
    }

    static class TestCase {
        public static int ANS = 3;
        public static TreeNode NODE = TreeNode.deserialize("[3,5,1,6,2,0,8,#,#,7,4]");
        public static int O1 = 5;
        public static int O2 = 1;
    }
}
